package chapter9.sort;

/**
 * Created by lili on 2017/7/1.
 */
//【例9.1】 随机数序列的直接插入排序。

public class IntRandom                                     //将随机数序列进行排序
{
    public static int[] random(int n)                      //产生n个随机数，返回整型数组
    {
        if (n<=0)
            return null;
        int table[] = new int[n];
        for (int i=0; i<table.length; i++)
            table[i] = (int)(Math.random()*100);           //产生一个0～99之间的随机数
        return table;                                      //返回一个数组
    }

    public static void main(String[] args)
    {
//    	int[] table = {32,26,87,72,26,17};                 //直接插入排序图9-1
        int[] table = IntRandom.random(9);
//      int[] table = {27,38,65,97,76,13,27,49,55,4};      //9.2.2希尔排序图9-2

//    	int[] table = {32,26,87,72,26,17};                 //冒泡排序,图9-2
//    	int[] table = {1,2,3,4,5,6,7,8};                   //冒泡排序，快速排序，最小堆
//    	int[] table = {1,3,2,4,5,8,6,7};                   //冒泡排序
//    	int[] table = {4,5,8,1,2,7,3,6};                   //冒泡排序
//    	int[] table = {8,7,6,5,4,3,2,1};                   //冒泡排序，快速排序
//    	int[] table = {38,26,97,19,66,1,5,49};             //快速排序 ,图9-5
//    	int[] table = {38,97,26,19,38,5};                  //直接选择排序,图9-7
//    	int[] table = {81,49,38,27,97,76,19,13};           //堆排序,图9-9
//    	int[] table = {36,74,68,61,55,15,4,12};        //堆排序
//        int[] table = {52,26,97,19,66,8,49};    	       //归并排序,图9-11

        //        int[] table = {49,65,13,81,76,97,38,49};
//      int[] table = {85,12,36,24,47,30,53,91,76};
        System.out.print("关键字序列: ");
        Array.print(table);
//        Array.insertSort(table);
//        Array.shellSort(table);
//        Array.bubbleSort(table);
//        Array.quickSort(table);
//        Array.selectSort(table);
//        Array.heapSort_min(table);
//        Array.heapSort_max(table);
        Array.mergeSort(table);

//      int[] table = {13,27,38,49,97,76,49,81};        //最小堆
//        int[] table = {9,13,62,69,76,92,96,72,96};        //最小堆
//        int[] table = {9,13,62,59,26,92,56,72,96};        //不是最小堆
//        System.out.println("最小堆序列? "+Array.isMinHeap(table));
//        int[] table = {94,85,74,58,7,20,60,26,35};        //最大堆
//        int[] table = {94,85,34,58,7,20,60,26,35};        //不是最大堆
//      int[] table = {97,81,38,76,49,27,19,13,65};        //最大堆
//        System.out.println("最大堆序列? "+Array.isMaxHeap(table));
    }
}


/*
程序运行结果如下：
关键字序列:  32 26 87 72 26 17                        //直接插入排序图9-1
直接插入排序
第1趟:  26 32 87 72 26 17
第2趟:  26 32 87 72 26 17
第3趟:  26 32 72 87 26 17
第4趟:  26 26 32 72 87 17                            //排序算法稳定
第5趟:  17 26 26 32 72 87


关键字序列:  27 38 65 97 76 13 27 49 55 4             //图9-2
希尔排序
delta=5   13 27 49 55 4 27 38 65 97 76
delta=2   4 27 13 27 38 55 49 65 97 76
delta=1   4 13 27 27 38 49 55 65 76 97


关键字序列:  32 26 87 72 26 17                        //图9-2
冒泡排序
第1趟排序:  26 32 72 26 17 87
第2趟排序:  26 32 26 17 72 87
第3趟排序:  26 26 17 32 72 87
第4趟排序:  26 17 26 32 72 87
第5趟排序:  17 26 26 32 72 87

关键字序列:  1 2 3 4 5 6 7 8
冒泡排序
第1趟排序:  1 2 3 4 5 6 7 8

关键字序列:  1 3 2 4 5 8 6 7
冒泡排序
第1趟排序:  1 2 3 4 5 6 7 8
第2趟排序:  1 2 3 4 5 6 7 8

关键字序列:  4 5 8 1 2 7 3 6
冒泡排序
第1趟排序:  4 5 1 2 7 3 6 8
第2趟排序:  4 1 2 5 3 6 7 8
第3趟排序:  1 2 4 3 5 6 7 8
第4趟排序:  1 2 3 4 5 6 7 8
第5趟排序:  1 2 3 4 5 6 7 8

关键字序列:  8 7 6 5 4 3 2 1
冒泡排序
第1趟:  7 6 5 4 3 2 1 8
第2趟:  6 5 4 3 2 1 7 8
第3趟:  5 4 3 2 1 6 7 8
第4趟:  4 3 2 1 5 6 7 8
第5趟:  3 2 1 4 5 6 7 8
第6趟:  2 1 3 4 5 6 7 8
第7趟:  1 2 3 4 5 6 7 8


关键字序列:  38 26 97 19 66 1 5 49                    //快速排序图9-5
0..7,  vot=38   5 26 1 19 38 66 97 49
0..3,  vot=5   1 5 26 19 38 66 97 49
2..3,  vot=26   1 5 19 26 38 66 97 49
5..7,  vot=66   1 5 19 26 38 49 66 97

关键字序列:  1 2 3 4 5 6 7 8
0..7,  vot=1   1 2 3 4 5 6 7 8
1..7,  vot=2   1 2 3 4 5 6 7 8
2..7,  vot=3   1 2 3 4 5 6 7 8
3..7,  vot=4   1 2 3 4 5 6 7 8
4..7,  vot=5   1 2 3 4 5 6 7 8
5..7,  vot=6   1 2 3 4 5 6 7 8
6..7,  vot=7   1 2 3 4 5 6 7 8

关键字序列:  8 7 6 5 4 3 2 1
0..7,  vot=8   1 7 6 5 4 3 2 8
0..6,  vot=1   1 7 6 5 4 3 2 8
1..6,  vot=7   1 2 6 5 4 3 7 8
1..5,  vot=2   1 2 6 5 4 3 7 8
2..5,  vot=6   1 2 3 5 4 6 7 8
2..4,  vot=3   1 2 3 5 4 6 7 8
3..4,  vot=5   1 2 3 4 5 6 7 8


关键字序列:  38 97 26 19 38 5                         //图9-7
直接选择排序
第1趟:  5 97 26 19 38 38
第2趟:  5 19 26 97 38 38
第3趟:  5 19 26 97 38 38
第4趟:  5 19 26 38 97 38
第5趟:  5 19 26 38 38 97

关键字序列:  81 49 38 27 97 76 19 13                //堆排序,图9-9
最小堆？ false
建立最小堆序列
sift  3..7   81 49 38 13 97 76 19 27
sift  2..7   81 49 19 13 97 76 38 27
sift  1..7   81 13 19 27 97 76 38 49
sift  0..7   13 27 19 49 97 76 38 81
最小堆？ true
堆排序（降序）
sift  0..6   19 27 38 49 97 76 81 13
sift  0..5   27 49 38 81 97 76 19 13
sift  0..4   38 49 76 81 97 27 19 13
sift  0..3   49 81 76 97 38 27 19 13
sift  0..2   76 81 97 49 38 27 19 13
sift  0..1   81 97 76 49 38 27 19 13
sift  0..0   97 81 76 49 38 27 19 13

最小堆
关键字序列:  81 49 76 27 97 38 49 13 65              //图9-8
sift  3..8   81 49 76 13 97 38 49 27 65
sift  2..8   81 49 38 13 97 76 49 27 65
sift  1..8   81 13 38 27 97 76 49 49 65
sift  0..8   13 27 38 49 97 76 49 81 65
 13 27 38 49 97 76 49 81 65
sift  0..7   27 49 38 65 97 76 49 81 13
sift  0..6   38 49 49 65 97 76 81 27 13
sift  0..5   49 65 49 81 97 76 38 27 13
sift  0..4   49 65 76 81 97 49 38 27 13
sift  0..3   65 81 76 97 49 49 38 27 13
sift  0..2   76 81 97 65 49 49 38 27 13
sift  0..1   81 97 76 65 49 49 38 27 13
sift  0..0   97 81 76 65 49 49 38 27 13

最大堆
关键字序列:  49 65 13 81 76 27 97 38 49
sift  3..8   49 65 13 81 76 27 97 38 49
sift  2..8   49 65 97 81 76 27 13 38 49
sift  1..8   49 81 97 65 76 27 13 38 49
sift  0..8   97 81 49 65 76 27 13 38 49
 97 81 49 65 76 27 13 38 49
sift  0..7   81 76 49 65 49 27 13 38 97
sift  0..6   76 65 49 38 49 27 13 81 97
sift  0..5   65 49 49 38 13 27 76 81 97
sift  0..4   49 38 49 27 13 65 76 81 97
sift  0..3   49 38 13 27 49 65 76 81 97
sift  0..2   38 27 13 49 49 65 76 81 97
sift  0..1   27 13 38 49 49 65 76 81 97
sift  0..0   13 27 38 49 49 65 76 81 97

关键字序列:  52 26 97 19 66 8 49                      //图9-11
归并排序
子序列长度n=1   26 52 19 97 8 66 49
子序列长度n=2   19 26 52 97 8 49 66
子序列长度n=4   8 19 26 49 52 66 97

关键字序列:  13 27 38 49 97 76 49 81 65
最小堆序列? true

*/

